package course.p3_arraysSort.exa08_heapSort;

import org.junit.Test;

import java.lang.reflect.Array;
import java.util.Arrays;

public class HeapSort {
    /**
     * 堆数据结构实现，此部分内容目前有点超纲，
     * 待学习完 二叉树 再来看这个排序方法
     * @param <T>
     */
    public static class Heap<T extends Comparable<T>> {

        public T[] array;//存储元素的数组
        public int count;//描述堆中存在元素的个数
        public int capacity;//堆的大小
        // 0-最大堆, 1-最小堆
        public int heap_type;

        //创建堆构造方法
        public Heap(int capacity,int heap_type) {
            this.capacity = capacity;
            this.heap_type = heap_type;
            this.count = 0;
        }

        //得到父母节点的位置
        public int Parent(int i) {
            if(i<=0||i>this.count)
                return -1;
            return (i-1)/2;
        }
        //得到左孩子节点的位置
        public int LeftChild(int i) {
            int left=2*i+1;
            if(left>=this.count)
                return -1;
            return left;
        }
        //得到右孩子节点的位置
        public int RightChild(int i) {
            int right=2*i+2;
            if(right>=this.count)
                return -1;
            return right;
        }
        //堆化元素
        public void PercolateDown(int i) {
            int l,r,max;
            T temp;
            l=LeftChild(i);
            r=RightChild(i);
            if(l==-1&&r==-1)
                return;
            if(l!=-1&&this.array[l].compareTo(this.array[i])>0)
                max=l;
            else
                max=i;
            if(r!=-1&&this.array[r].compareTo(this.array[max])>0)
                max=r;

            if(max==i)
                return;
            else
            {
                temp=this.array[i];
                this.array[i]=this.array[max];
                this.array[max]=temp;
            }
            PercolateDown(max);
        }

        //扩展堆
        void ResizeHeap() {
            T [] array_old= (T[]) Array.newInstance(array[0].getClass(),capacity);
            //复制方法
            System.arraycopy(this.array,0,array_old,0,this.count-1);
            this.array= (T[]) Array.newInstance(array[0].getClass(),this.capacity*2);

            for(int i=0;i<this.capacity;i++) {
                this.array[i] = array_old[i];
            }
            this.capacity *=2;
        }

        //数组建堆
        void BuildHeap(Heap<T> h, T[] A, int n) {
            this.array = (T[]) Array.newInstance(A[0].getClass(),capacity);
            if(h==null) h = new Heap<T>(A.length,1);
            while(n>this.capacity)
                h.ResizeHeap();
            //数组赋值
            for(int i=0;i<n;i++){
                h.array[i]=A[i];
            }
            this.count=n;

            for(int i=(n-1)/2;i>=0;i--)//节点堆化
                h.PercolateDown(i);
        }

        /**
         *
         * @param h
         * @param A
         * @param n
         * @return
         */
        T[] Heapsort(Heap<T> h, T[] A, int n) {
            int i;
            T temp;
            BuildHeap(h,A,n);
            h.count=n;
            for(i=n-1;i>=0;i--) {
                temp= (T) h.array[0];
                A[i]=temp;
                h.array[0] = h.array[h.count-1];
                h.count--;
                h.PercolateDown(0);
            }
            return A;
        }
    }

    @Test
    public void heapSortTest() {
        Integer[] a = {13,17,1,6,4,2,5};
        Heap<Integer> test = new Heap<>(a.length,0);
        a = test.Heapsort(test,a,a.length);
        System.out.println(Arrays.toString(a));
    }




}
